This invention relates in general to Galois Field arithmetic and more specifically to a single implementation of a multi-dimensional Galois Field multiplier.
Galois Field arithmetic finds application in error correcting codes, particularly Reed Solomon Codes and cryptographic codes.
Galois Field arithmetic is a cyclic finite field arithmetic such that any operation performed on any two numbers within the field, yields a number in the field, i.e. there is no operation which can be done on any two numbers within the field which yields a number outside of the field. Finite field arithmetic uses real numbers that consist of the range of numbers shown in Table 1 below. For example, the range of integers from 0 to 7 (0,1,2,3,4,5,6,7) has a Galois Field representation or notation of GF(8) because the Galois Field has 8 elements, while the range of integers 0 to 1 has a Galois Field of GF(2) because it has only two elements, etc. In addition, digital systems transmit data in bits. Because bits are binary, they can only take on one of two values, either a 0 or a 1. Grouping these bits together to build a symbol is common in digital systems. These groupings are all based on a power of two. Table 1 lists the digital symbols vs. GF notation.
There are several ways of representing the numbers in the finite field of any given Galois Field. For example, the data shown on Table 2 illustrates the integer, binary and polynomial representations of the numbers of GF(8).
In addition, each Galois Field has one or more primitive polynomials, or generator polynomials, which is analogous to a particular set of consecutive real integers which also has one or more prime numbers, depending upon how large is the particular set of consecutive integers. Primitive polynomials, p(x), g(x) are polynomials which are used to define the arithmetic functions for each field. For example, in Galois Field arithmetic, like arithmetic, certain mathematical properties exist such as laws of commutativity, associativity, etc. Therefore, when determining what is the sum or product of any two elements within a Galois Field, if after applying such laws, the sum or product will lie outside the Galois Field, that sum or product is divided by a predetermined primitive polynomial. In this way, the Galois Field is preserved. Table 3 lists the integer representation of all the primitive polynomials for GF(8) to GF(256).
As can be seen from the above table, there is only one primitive polynomial for GF(8) and GF(16), due to the smallness of the field, however, GF(128) has 9 primitive polynomials and GF(256) has 8 primitive polynomials. As mentioned previously, each of these integer representations has a corresponding polynomial representation. For example, one primitive polynomial, p(x) for GF(256) is 285, which corresponds to p(x)=x8+x4+x3+X2+1.
Multiplication in finite fields is easily computed using the polynomial format. For the following examples, GF(8) and p(x)=x3+x+1 are used to build the multiplication Tables 4 and 5. The primitive polynomial is used to reduce or xe2x80x98foldxe2x80x99 the product or on results back into the field. For example:
x2*x2=x4
where x4 is not a member of the GF(8) field. The primitive polynomial, p(x), is then used in a polynomial division to generate the remainder of:
x4/p(x)=x4/x3+x+1=x2+x
The same primitive polynomial is used to generate the entire multiplication table per GF, even if more than one primitive polynomial exists for a particular GF.
Another way of representing Table 4 is in binary as shown in Table 5, below:
Notice how each entry occurs once in each row or column. This set of numbers forms a field. The field has an identity of 001 and each entry in the field has an inverse (except zero) such that (a*inv a)=001. Because every element has in inverse, this group is called a field. The tables below illustrate the inverse in binary of GF(8), and then addition and subtraction tables for GF(8).
Similarly under addition, GF(8) using the same primitive polynomial 1011 is:
For addition and subtraction in GF(8), inspection determines that the elements of both Galois fields are identical and the operation is actually an Exclusive OR or XOR logic function. Again there is an identity element of 000 and each element has an inverse under addition/subtraction. As is illustrated in Table 9 below, all elements self-inverse under addition and subtraction.
As is illustrated in the previous binary GF(8) example, implementation of the add and subtract is trivial in a general purpose microprocessor, but the multiplication operator is a non-standard element in both general purpose processors and digital signal processors alike. The algorithm to perform multiplication in Galois field arithmetic is now described. Step 1: Perform polynomial (carryless) multiply of the two elements. Field size N elements produce a 2Nxe2x88x921 degree polynomial (which doesn""t fit in the field of N size elements), so, must perform Step 2: the result of the multiply is divided by the primitive polynomial and the remainder is the final answer. Step 2 has the following sub-parts: 1) Use the Most Significant Bit (MSB) of the result to determine whether to subtract (XOR) the primitive polynomial, P or not; and 2) Repeat the conditional subtract until the MSB of the result is in position Nxe2x88x921 or less (for a Galois field size of N). The above described Galois field multiply is illustrated in FIG. 1. As shown, first the two operands A(4:0) 32 and B(4:0) 34, of GF size GF(16), perform a polynomial multiply and yield a product 1000101 35. Because the MSB of the product 35 is a xe2x80x9c1xe2x80x9d, a division of the product by the primitive polynomial or generator polynomial 36 is performed yielding the xe2x80x9cremainderxe2x80x9d 38. Because, after the first conditional subtraction (XOR), the xe2x80x9cremainderxe2x80x9d 38 does not fit in a GF(16), another conditional subtraction is performed, yielding a remainder of the size of GF(16) which is the final result 39.
Galois Field (GF) multiplication is an important and necessary function, i.e. performed many times, in Reed-Solomon (RS) codes. RS codes are used in many communication applications such as satellites, modems, audio compact disks, and set-top boxes as a digital data transmission forward error correction tool. Each one of these applications has a different standard. Each standard defines a symbol size, a GF, and a primitive polynomial (generator polynomial). Each application requires a unique GF multiplier or a GF multiplier which has a unique configuration to be created which will at least depend on the symbol size, the size of the Galois Field and the primitive polynomial used. There has never been a GF multiplier which could implement all the different standards in a cost efficient manner.
An implementation of a multi-dimensional Galois Field multiplier for Galois Fields from a GF(1) up to a GF(256) is disclosed. This GF multiplier is able to support many different communication standards such as standards with different symbol sizes, different GFs, and different primitive polynomials. The key to allow a single implementation of a GF multiplier to perform for all different GF sizes is to align the input data such that the MSB is aligned to bit 7 in the GF(256) input data field. A polynomial multiply of the two input operands is performed. The product polynomial is then conditionally XORed with the primitive polynomial starting with the most significant bit, the condition being if the left most bit of the product being 1. In other words, if the product polynomial has a MSB of 1, then XOR the product with the primitive polynomial. The result of the division with the primitive polynomial yields a remainder. Perform this division by the primitive polynomial step until the condition is not satisfied or until the MSB is 0. In addition, for fields smaller than GF(256), the sequence of conditional XORs has to be ANDed with the a predetermined mask in dependence upon the size of the GF. The field polynomial is aligned left and the result is also aligned left.